/*
 * Copyright (C), 2015-2018
 * FileName: Solution020
 * Author:   zhao
 * Date:     2018/7/31 15:28
 * Description: 有效的括号
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredone;

import java.util.HashMap;
import java.util.Stack;

/**
 * 〈一句话功能简述〉<br>
 * 〈有效的括号 〉
 *
 * @author zhao
 * @date 2018/7/31 15:28
 * @since 1.0.1
 */
public class Solution020 {

  /**************************************
   * 题目
   * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
   *
   * 有效字符串需满足：
   *
   * 左括号必须用相同类型的右括号闭合。
   * 左括号必须以正确的顺序闭合。
   * 注意空字符串可被认为是有效字符串。
   *
   * 示例 1:
   *
   * 输入: "()"
   * 输出: true
   * 示例 2:
   *
   * 输入: "()[]{}"
   * 输出: true
   * 示例 3:
   *
   * 输入: "(]"
   * 输出: false
   * 示例 4:
   *
   * 输入: "([)]"
   * 输出: false
   * 示例 5:
   *
   * 输入: "{[]}"
   * 输出: true
   **************************************/

  /**************************************
   *
   * 想法：
   *  没有想出来使用什么方法去完成
   *  想了几个点
   *    1.首先是长度，单数的话直接返回失败
   *    2.暴力遍历，好像也不行
   *  后来是看了提示，可以使用栈
   *
   * 我的做法
   * 超过24.51%的测试案例
   *
   * ***********************************/
  public boolean isValid(String s) {
    HashMap<Character, Character> characterHashMap = new HashMap<Character, Character>();
    characterHashMap.put(')', '(');
    characterHashMap.put(']', '[');
    characterHashMap.put('}', '{');

    Stack<Character> characters = new Stack<Character>();
    char[] chars = s.toCharArray();

    for (int i = 0; i < chars.length; i++) {
      Character c = chars[i];
      if ('(' == c || '[' == c || '{' == c) {
        characters.push(c);
        continue;
      }
      if (')' == c || ']' == c || '}' == c) {
        Character companionChar = characterHashMap.get(c);
        //判断是否和栈顶的数据一致
        //这里使用pop而不适用peek
        if (characters.empty() || !companionChar.equals(characters.pop())) {
          return false;
        }
      }
    }
    return characters.empty();
  }

  /**************************************
   * 比我好的答案
   *
   * 没有使用hashMap
   *
   *
   * ***********************************/
  public boolean better(String s) {
    Stack<Character> ch = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      if (c == '(' || c == '[' || c == '{') {
        ch.push(c);
      } else {
        if (ch.isEmpty()) {
          return false;
        }

        char topChar = ch.pop();
        if (c == ')' && topChar != '(') {
          return false;
        } else if (c == ']' && topChar != '[') {
          return false;
        } else if (c == '}' && topChar != '{') {
          return false;
        }
      }
    }

    return ch.isEmpty();

  }

}
